﻿//给定一个含有 n 个正整数的数组和一个正整数 target 。
//
//找出该数组中满足其总和大于等于 target 的长度最小的 子数组
//[numsl, numsl + 1, ..., numsr - 1, numsr] ，并返回其长度。
//如果不存在符合条件的子数组，返回 0 。
//
//输入：target = 7, nums = [2, 3, 1, 2, 4, 3]
//输出：2
//解释：子数组[4, 3] 是该条件下的长度最小的子数组。
//
//输入：target = 4, nums = [1, 4, 4]
//输出：1
//
//输入：target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
//输出：0
//
//提示：
//	1 <= target <= 10^9
//	1 <= nums.length <= 10^5
//	1 <= nums[i] <= 10^4


// class Solution {
// public:
//     int minSubArrayLen(int target, vector<int>& nums) {
//         // 记录结果
//         int ret = INT_MAX;
//         int n = nums.size();
//         // 枚举出所有满⾜和⼤于等于target的⼦数组[start, end]
//         // 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩

//         // 枚举开始位置

//         for (int start = 0; start < n; start++) {
//             int sum = 0; // 记录从这个位置开始的连续数组的和

//             // 寻找结束位置

//             for (int end = start; end < n; end++) {
//                 sum += nums[end]; // 将当前位置加上

//                 if (sum >= target) // 当这段区间内的和满⾜条件时

//                 {
//                     // 更新结果start开头的最短区间已经找到

//                     ret = min(ret, end - start + 1);
//                     break;
//                 }
//             }
//         }
//         // 返回最后结果

//         return ret == INT_MAX ? 0 : ret;
//     }
// };

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, len = INT_MAX;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right]; // 进窗⼝

            while (sum >= target) // 判断
            {
                len = min(len, right - left + 1); // 更新结果

                sum -= nums[left++]; // 出窗⼝
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};
